package com.example.demo.class15_并查集;


/**
 * @program: java_base
 * @description: 并查集
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/28 14:33
 * [力扣地址](https://leetcode.com/problems/friend-circles/)
 * 可以理解为 二维数组  N * N 代表每个人的关系
 * 认识多少人，连接起来也算认识
 * 只遍历右上部分即可。
 * m[i][j] 认识 那么 m[j][i] 也认识！
 * m[i][j] 认识 m[j][k] 认识 那么 m[i][k] 也认识
 * m[i][i] 认为是自己认识自己
 * 求：有多少个朋友圈？即 有多少个岛？ 多少个联通区？
 *
 * 提示：
 *      1 <= n <= 200
 *      n == isConnected.length
 *      n == isConnected[i].length
 *      isConnected[i][j] 为 1 或 0
 *      isConnected[i][i] == 1
 *      isConnected[i][j] == isConnected[j][i]
 *   [[1,0,0],[0,1,0],[0,0,1]]
 *   1  0   0
 *   0  1   0
 *   0  0   1
 *   结果 3
 *
 * 、、、、、、、、
 *   [[1,1,0],[1,1,0],[0,0,1]]
 *  1   1   0
 *  1   1   0
 *  0   0   1
 *  结果 2
 *  有效集合： 第一组：(0,0)(0,1)(1,1) 和 (2,2) 这两组
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-provinces
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code01_FriendCirclesDemo<V> {


    /**
     * 入口函数
     *
     * @param isConnected
     * @return
     */
    public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        UnionFind unionFind = new UnionFind(N);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.sets;
    }


    /**
     * 底层使用数组形式实现并查集结构！
     * 表形式：hashMap O（1）具有较大的常数项！属于最优解范畴，但是时间可能用时较多
     * 顾改造为数组结构
     */
    public static class UnionFind {
        // 自己的父级是
        int[] parent;
        // 头结点 自身的节点数
        int[] headSize;
        // 辅助结构
        int[] help;
        // 内有多少 结构
        int sets;

        UnionFind(int N) {
            // 初始化，具有这么多个父节点
            parent = new int[N];
            headSize = new int[N];
            help = new int[N];
            sets = N;
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                headSize[i] = 1;
            }
        }


        /**
         * @param a 要寻找到 此节点的 head
         * @return 返回a 的 head 索引
         * @desc 用于查找节点a 的 head 并且优化结构
         */
        public int findHead(int a) {
            int cur = a;
            int i = 0;
            while (parent[cur] != cur) {
                help[i++] = cur;
                cur = parent[cur];
            }

            for (i--; i >= 0; i--) {
                parent[help[i]] = cur;
            }
            return cur;
        }

        public void union(int i, int j) {
            int f1 = findHead(i);
            int f2 = findHead(j);
            if (f1 != f2) {
                int i1Size = headSize[f1];
                int i2Size = headSize[f2];
                if (i1Size >= i2Size) {
                    parent[f2] = f1;
                    headSize[f1] = i1Size + i2Size;
                } else {
                    parent[f1] = f2;
                    headSize[f2] = i1Size + i2Size;
                }
                sets--;
            }
        }
    }
}
